Memory cells dynamically allocated for the use of an application usually change with time, on account of the execution of the application, so that they become inaccessible to the application. A memory cell is regarded as garbage if the application can no longer access it along any route. Garbage collection denotes an automatic system with which the memory space occupied by such memory cells is restored for the use of an application. Thus, the garbage collector must distinguish garbage from among live memory cells. The last-mentioned denotes memory cells which can still be accessed by the application and which the application will possibly still use. Garbage collectors determine live memory cells typically so that these are cells that can be accessed from the root set of the memory by tracking pointers stored in the memory. A root set denotes data that is immediately accessible to a program without tracking any pointer trail.
Garbage collection increases the reliability of programs, since for example memory management errors can be eliminated thereby.
In copying garbage collection, garbage is not actually collected but live memory cells are transferred (copied) from their location area to a new storage area that is normally contiguous. The original storage area can thereafter be freed for the use of the application, since all live memory cells in said area have been transferred elsewhere. Copying garbage collection methods are generally considered to be quite effective. An important advantage thereof is that they are compacting, thus allowing prevention of memory fragmentation.
A currently common trend is to carry out garbage collection in generations. In such a system, the memory is divided into several areas according to age (generations), and collection is performed more frequently in the younger generations than in the older generations, since in the younger generations the memory cells turn into garbage in greater likelihood (more rapidly) than in the older generations. Thus, garbage collection in the younger generations enables more efficient freeing of memory (more freed memory for the same amount of work). A further principal drawback of non-generational copying garbage collection methods is also that the same memory cells must be copied again in every collecting cycle, since some of the memory cells remain alive from one collecting cycle to another. Then part of the time of the garbage collector is taken up by repeatedly copying the same memory cells. Generational garbage collection also enables the majority of such repeated copying to be avoided.
The present invention relates to generational garbage collection of this kind in a central memory database which, furthermore, is recoverable. A central memory database, or a database in short, denotes in this context a specific main storage area that is normally contiguous. Recovery, on the other hand, means that data resident in the central memory is also written into a disk memory, and hence in a failure situation, such as a power outage, the situation that was prevalent in the central memory at the time of failure can be reconstructed using the data stored in the disk memory.
The method of the invention is specifically intended for applications in which real-time performance and reliability are essential characteristics. As was stated above, one field of application is constituted by network elements of a communications network. At telephone exchanges, for example, it must be possible to carry out garbage collection as efficiently as possible so that it does not create any extra delay to the existing connections or connection setup processes in progress.
In known systems with disk back-up, so-called remembered sets and possibly also a plurality of other auxiliary structures are maintained as back-up on disk in view of a possible failure, so that the database may be reconstructed after the failure. In such systems, the amount of disk writing due to garbage collection is very high. In connection with recovery, the remembered sets and possible other auxiliary structures stored for example in logs are examined, and the state of the remaining database is updated to correspond to that preceding the failure. A further drawback of such known systems is that the amount of data resulting from back-up is high compared with the memory capacity occupied by payload data.
Hence, a considerable problem in systems with disk back-up requiring maximum real-time performance is how the disk traffic resulting from back-up (mainly writing onto disk) should be handled so as to produce as little delay as possible to the operation of the system. In view of back-up it would naturally be preferable if the amendments in the central memory could be entered on disk immediately, but this is not possible in view of the efficiency of the system, since in practice disk traffic would increase far too much and would excessively retard the operation of the system. From the point of view of the efficiency of the system, particularly small amendments that occur often are problematic, since the operation of the disk memory is retarded considerably if the write head must be repeatedly moved from one location to another. Thus, as much sequential data as possible should be written into the disk memory at a time. Thus, in order to optimize the disk traffic, attention should be paid in addition to the quantity of disk traffic, also to the fact that the writing transactions onto disk can be carried out as continuously as possible and the number of writing cycles can be maintained low.
The problem is thus how garbage collection should be performed in such a way that a large main storage area can be backed up to disk, maintaining the performance of the system as good as possible.